package com.leetCode.four;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Set;

public class Problem42_1 {

	public static void main(String[] args) throws Exception {
		 Solution s = getInstance();
		 
//		 int[] test = {2,0,2};
		 int[] test = {5,4,1,2};
		 int[] test2 = new int[500];
		 for (int i = 0; i < test2.length; i++) {
			 test2[i] = (int) (Math.random()*100000);
		}
		 System.out.println("的mo");
//		 int[] test = {4,2,3};
		 int trap = s.trap(test2);
		 
		 
		 System.out.println("最终结果"+trap);
//{3=[7], 2=[3, 8, 10], 1=[1, 4, 6, 9, 11], 0=[0, 2, 5]}

	}
	
	class Solution {
	    public int trap(int[] height) {
	    	int exit = height.length;
	    	for (int i = 0; i < height.length; i++) {
	    		if(height[i]<=0){
	    			exit--;
	    		}
			}
	    	if(exit<=1){
	    		return 0;
	    	}
	    	//计算所有大于1的都当做1
	    	int count = 0;
	    	int left = -1;
	    	int right = height.length;
	    	//判断非0数中间有多少个0
	    	for (int i = 0; i < height.length; i++) {
				if(height[i]!=0){
					left = i;
					break;
				}
			}
	    	for (int i = height.length-1; i >= 0 ; i--) {
				if(height[i]!=0){
					right = i;
					break;
				}
			}
	    	for(int i=left; i<=right; i++){
	    		if(height[i] == 0){
	    			count++;
	    		}
	    	}
//	    	System.out.println(left+":"+right);
//	    	System.out.println(Arrays.toString(height)+":"+count);
	    	for (int i = 0; i < height.length; i++) {
	    		height[i] = (height[i]-1)>0?(height[i]-1):0;
			}
	    	return count+trap(height);
	    }
	}
	
	static Solution getInstance() throws Exception{
		String className = Thread.currentThread().getStackTrace()[1].getClassName();
		Class<?> forName = Class.forName(className);
		Method method = forName.getMethod("newS", null);
		Solution solution = (Solution) method.invoke(forName.newInstance(),null);
		return solution;
	}
	
	public Solution newS(){
		return new Solution();
	}
	
}
